package org.wj.problem

object SearchInsert{

  def main(args: Array[String]): Unit = {
    val i = searchInsert(Array(1,4,6,7,8,9),6)
    print(i)
  }

  def searchInsert(nums: Array[Int], target: Int): Int = {
    binarySearch(0, nums.length, target, nums)
  }

  def binarySearch(start: Int, end: Int, target: Int, array: Array[Int]): Int = {
    if(array.length==0) return 0
    if(array(0)>=target) return 0
    if(array(array.length-1)<target) return array.length

    val mid: Int = (start + end) / 2
    if (target==array(mid))
      return mid

    if (target > array(mid) && target < array(mid+1))
      return mid + 1

    if (target < array(mid) && target > array(mid - 1))
      return mid
    if (target<array(mid))
      return binarySearch(start, mid-1, target, array)
    else(target>array(mid))
    binarySearch(mid+1, end, target, array)
  }


}